package barbre;

import java.io.*;
import java.util.*;
public class ArbreB implements Serializable{
	protected Noeud racine;
	protected final int degreMin;
	private int nbMot;
	public ArbreB(int t) {
		Noeud maillon = new Noeud (t);
		degreMin = t;
		maillon.setFeuille(true);
		maillon.setNbCles(0);
		racine = maillon;
	}
	protected int getDegreMin() {
		return degreMin;
	}
	public Noeud getRacine(){
		return racine;
	}
	protected void bArbreDecouperFils(Noeud x, int i, Noeud y) {
		Noeud z = new Noeud (degreMin);
		z.setFeuille(y.getFeuille());
		z.setNbCles(degreMin - 1);
		for (int j = 1; j <= (degreMin - 1); j++) {
			z.insererTabCles(j, y.getTabCles(j + degreMin));
		}
		if (y.getFeuille() == false) {
			for (int j = 1; j <= degreMin ; j++) {
				z.insererTabFils(j,
						y.getTabFils(j + degreMin));
			}
		}
		y.setNbCles(degreMin - 1);
		y.setTabClesNull(y.getNbCles());
		for (int j = x.getNbCles() + 1; j >= i + 1; j--) {
			x.insererTabFils(j + 1, x.getTabFils(j));
		}
		x.insererTabFils(i + 1, z);
		for (int j = x.getNbCles(); j >= i; j--) {
			x.insererTabCles(j + 1, x.getTabCles(j));
		}
		x.insererTabCles(i, y.getTabCles(degreMin));
		x.setNbCles(x.getNbCles() + 1);
	}
	protected void bArbreInsererIncomplet(Noeud x, Object o, Comparator c) {
		int i = x.getNbCles();
		if (x.getFeuille() == true) {
			while ((i >= 1) && ( c.compare(o,x.getTabCles(i) ) < 0)) { //faut voir le cas ou on peut avoir deux mots semblables... ie ==0
				x.insererTabCles( i + 1, x.getTabCles (i));
				i = i - 1;
			}
			x.insererTabCles(i + 1, o);
			x.setNbCles(x.getNbCles() + 1);
		} else {
			while ((i >= 1) && (c.compare(o,x.getTabCles(i) ) < 0) ) {
				i = i - 1;
			}
			i = i + 1;
			if (x.getTabFils(i).getNbCles() == 2 * degreMin - 1) {
				bArbreDecouperFils(x, i, x.getTabFils(i));
				if (c.compare(o,x.getTabCles(i) ) > 0)
					i = i + 1;
			}
			bArbreInsererIncomplet(x.getTabFils(i), o,c);
		}
	}
	public Object bArbreRechercher(Noeud x, Comparator c , Object o ) {
		int i = 1;
		while ((i <= x.getNbCles()) &&
				(c.compare(x.getTabCles(i),o)
						> 0)) {
			i = i + 1;
		}
		if ((i <= x.getNbCles()) &&
				(c.compare(x.getTabCles(i),o)
						== 0)) {
			return x.getTabCles(i);
		}
		if (x.getFeuille() == true) {
			return null;
		} else {
			return bArbreRechercher(x.getTabFils(i),c,o);
		}
	}
	// public abstract void findSameElement(Object o);
	public void bArbreInserer(Object o,Comparator c) {
		// a trouvé ou mettre le rajout quand pas encore d'occurence
		if (contientElement(o,c) != true) {
			Noeud r = this.racine;
			if (r.getNbCles() == 2 * degreMin - 1) {
				Noeud s = new Noeud (degreMin);
				this.racine = s;
				s.setFeuille(false);
				s.setNbCles(0);
				s.insererTabFils(1, r);
				bArbreDecouperFils(s, 1, r);
				bArbreInsererIncomplet(s,o,c);
			} else {
				bArbreInsererIncomplet(r, o,c);
			}
		}
	}
	public boolean contientElement(Object o , Comparator c) {
		if (bArbreRechercher(this.racine,c,o ) == null) {
			return false;
		} else {
			return true;
		}
	}
	public void afficheArbre (Noeud x) {
		for (int i = 1; i <= x.getNbCles() + 1; i++) {
			if (x.getTabFils(i) != null)
				afficheArbre(x.getTabFils(i));
			for (int j = 1; j <= x.getNbCles(); j++) {
				System.out.println( x.getTabCles(j) );
			}
			return ;
		}
	}
	public void trie(Noeud x,Comparator c) {
		for (int i = 1; i <= x.getNbCles() + 1; i++) {
			if (x.getTabFils(i) != null)
				trie(x.getTabFils(i),c);
			for (int j = 1; j <= x.getNbCles(); j++) {
				bArbreInserer(x.getTabCles(j),c);
			}
			return ;
		}
	}
	public static void main(String args[]) {
		ArbreB ar = new ArbreB(5);
	
	}
}

